Joint rate control and scheduling for providing bounded delay with high efficiency in multihop wireless networks

摘要

This thesis considers the problem of supporting traffic with elastic bandwidth requirements and hard end-to-end delay constraints in multi-hop wireless networks, with focus on source transmission rates and link data rates as the key resource allocation decisions. Specifically, the research objective is to develop a source rate control and scheduling strategy that guarantees bounded average end-to-end queueing delay and maximises the overall utility of all incoming traffic, using network utility maximisation framework. The network utility maximisation based approaches to support delay-sensitive traffic have been predominantly based on either reducing link utilisation, or approximation of links as M/D/1 queues. Both approaches lead to unpredictable transient behaviour of packet delays, and inefficient link utilisation under optimal resource allocation. On the contrary, in this thesis an approach is proposed where instead of hard delay constraints based on inaccurate M/D/1 delay estimates, traffic end-to-end delay requirements are guaranteed by proper forms of concave and increasing utility functions of their transmission rates. Specifically, an alternative formulation is presented where the delay constraint is omitted and sources’ utility functions are multiplied by a weight factor. The alternative optimisation problem is solved by a distributed scheduling algorithm incorporating a duality-based rate control algorithm at its inner layer, where optimal link prices correlate with their average queueing delays. The proposed approach is then realised by a scheduling algorithm that runs jointly with an integral controller whereby each source regulates the queueing delay on its paths at the desired level, using its utility weight coefficient as the control variable. Since the proposed algorithms are based on solving the alternative concave optimisation problem, they are simple, distributed and lead to maximal link utilisation. Hence, they avoid the limitations of the previous approaches. The proposed algorithms are shown, using both theoretical analysis and simulation, to achieve asymptotic regulation of end-to-end delay given the step size of the proposed integral controller is within a specified range.